密码学中的承诺原语（Commitment Scheme）与经典方案（上）

1

背景介绍

让我们考虑以下情况：Alice在佳士得（Christie's）购买Banksy的最后一件杰作，在这之前，她会确保艺术品在售出后不会被销毁。

佳士得选择了维克里封闭竞标的拍卖方式，这是一种相当常见的做法，其工作原理主要是：每个参与者都提交一个秘密的竞标。一旦所有的竞标都提交完毕，出价最高的一方获得该物品，支付的价格是第二高的竞标。

承诺方案正好解决了这个问题：它们允许安全地承诺一个秘密值，并在之后打开(Open)它，以便第三方可以检查承诺是否与打开的值一致。

本文将从基本的承诺方案（如基于哈希的承诺）开始，逐步加深，并介绍目前经常使用的Pedersen和Elgamal承诺。

下一章我们将着重介绍区块链中目前正在研究的承诺方案，包括前量子安全的承诺方案，最后将给大家简单介绍一下向量承诺（Vector Commitment, VC)。

2

承诺方案的定义和性质

承诺方案包括两个阶段，即承诺和公开，涉及一个确定性多项式时间算法。

(1). 承诺阶段：在这个阶段，发送方通过计算c = Comm(u, m)将m的二进制值提交给二进制u，并将c发送给接收方，接收方将结果存储以供稍后检查。

(2). 公开阶段：在这个阶段，发送方通过与接收方共享u和m来打开c，接收方自行计算c' = Comm(u, m)并检查c' = c。

在承诺的消息是一个位的特殊情况下，我们将讨论位承诺方案。

我们需要以下属性：

(1). 它必须隐藏，意味着由Comm(u, 0)和Comm(u, 1)引起的分布是不可区分的。换句话说：Comm不透露关于m的任何信息。

(2). 它必须绑定，意味着对于任何对手，获得Comm(u, 0) = Comm(u', 1)的概率在两个随机二进制u和u'上是可以忽略的。这意味着发送方输出一个提交，后来可以打开为两个不同的消息是不可行的。

如果对手受限于概率多项式时间算法，则承诺方案被称为计算隐藏或绑定，否则，该方案将被称为完全隐藏或绑定。

拥有既完全绑定又隐藏的承诺方案是非常困难的，因为想象一下承诺方案是信息理论上绑定的，意味着找不到随机二进制u和u'使得：

否则，发送方将能够计算出u和u'，并随意打开承诺。然而，如果发送方通过计算c = Comm(u, 0)来承诺0，接收方将会通过穷举法发现没有u'使得c = Comm(u', 1)，因此接收方将知道承诺的位是0，该方案将不具备隐藏性。

3

预备知识

如果遵循以下两个方法，我们可以很容易地创建承诺方案，其优点在于创建高效且具有良好隐藏和绑定特性的方案。

创建承诺方案的一种方法是使用抗碰撞哈希函数H，并定义一个计算上绑定和隐藏的承诺方案，具体如下：

1. 通过设置c = Comm(u, m) = H(u||m)对任何消息m进行承诺。

2. 通过揭示(u, m)并检查等式c = H(u||m)是否成立来打开承诺。

另一种创建承诺方案的方法是使用对称或非对称的加密系统，即：在这种方案中，我们生成公钥和私钥对(sk, pk)，然后删除私钥sk（出于安全考虑，否则我们可以简单地解密承诺的值）。

为了承诺一个值m，用户会抽样一些随机参数r并输出。

要打开承诺c，我们会揭示（m，r）并检查。

4

常用的承诺--Pedersen  和 Elgamal

这是密码学中一个活跃的话题，尤其在区块链技术和保密交易中被证明特别有用。我们可以找到几种常用的承诺方案，包括Damgard-Groth承诺、Gennaro承诺、MacKenzie-Yang方案、Galindo-Garcia-Van Rossum承诺和Naor承诺。

然而，我们关注两个在区块链中特别常用的承诺方案：Pedersen承诺和Elgamal承诺（文献中也拼写为ElGamal）。

Pedersen承诺

在这个承诺方案中，我们有以下设置：假设q是一个素数，G是一个阶为q的循环群，有两个生成元g和y。

为了承诺于m ∈ Zq，发送者选择均匀随机元素r ∈ Zq，并输出

为了打开一个承诺c，发送者揭示对(m, r)。如果接收者接受对m的打开，则满足条件

观察到，如果群G在离散对数假设下是安全的，那么这个承诺是完美隐藏的且计算上绑定的。

Elgamal承诺

在这种情况下，假设和Pedersen承诺一样，G是一个循环群的素数阶q，并且给定两个生成元g和y。

为了承诺于一个元素m ∈ G，随机选择r ∈ Zq，并计算

为了打开一个承诺c，发送者揭示对(m, r)。如果接收者接受对m的打开，则满足条件

我们观察到Elgamal承诺承诺于G的元素，而Pedersen承诺承诺于Zq的元素。关于性质，Elgamal承诺是完美绑定的但计算上隐藏的。

5

总结

本文我们主要介绍了承诺方案（Commitment Scheme）的定义，随后通过一个简单的基于哈希函数的承诺方案，简单介绍了一下承诺方案需要满足的几个性质，最后介绍了一下区块链中常用的两种方案，Pedersen和Elgamal承诺。

在后一节，我们将重点介绍目前承诺方案的一些研究进展，及向量承诺的概念和定义。

作者: Ramsès Fernàndez-València

翻译： 杨赟博

来源：https://medium.com/iovlabs-innovation-stories/commitment-schemes-4f3590be8c5

分享仅供学习参考，若有不当，请联系我们处理

END

热文推荐